package me.zk;

import java.util.Arrays;

/**
 * 冒泡排序（四）
 * 鸡尾酒排序(左一轮右一轮)
 * 用于大部分元素已经有序的情况下
 * @Author: zhang kai
 * @Date: 2022/06/27
 * @Description:
 */
public class BubbleSortDemo4 {

    public static void main(String[] args) {
        int[] array = {2,3,4,5,6,7,1,8,9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }


    public static void sort(int[] array) {
       int tmp = 0;
        //控制循环次数
        for (int i = 0; i < array.length / 2 ; i++) {
            //判断内层遍历是否有交换，如果无交换那么说明已经有序
            boolean isSorted = true;
            //奇数轮，从左向右比较和交换
            for (int j = i; j <  array.length  -i -1; j++) {
                if (array[j] > array[j+1]) {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //有元素交换，不是有序的
                    isSorted = false;
                }
            }
            if(isSorted) {
                break;
            }
            //偶数轮之前，将isSorted重新标价为true
            for (int j = array.length - i -1; j>i; j--) {
                if (array[j] < array[j-1]) {
                    tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    //有元素交换，不是有序的
                    isSorted = false;
                }
            }
            if(isSorted) {
                break;
            }
        }
    }
}
